//
// Created by bleedingfight on 2020/6/29.
//
#include "rebuildTree.h"
TreeNode* rebuildTree(std::vector<int>& preorderNums,
                      std::vector<int>& inorderNums, int startPreorder,
                      int endPreorder, int startInorder, int endInorder) {
  int rootValue = preorderNums[startPreorder];
  TreeNode* root = new TreeNode(rootValue);

  if (startInorder == endInorder) {
    // 如果中序已经遍历到最后一个元素，而且最后这个元素和前序的元素相同则递归结束
    if (startInorder == endInorder &&
        preorderNums[startPreorder] == inorderNums[startInorder])
      return root;
  }
  // 找到中序序列的根节点位置
  int inorder_index = startInorder;
  for (; inorder_index < inorderNums.size() - 1; inorder_index++) {
    if (inorderNums[inorder_index] == rootValue) break;
  }
  int leftTreeLength = inorder_index - startInorder;
  int leftTreerEnd = leftTreeLength + startPreorder;
  if (leftTreeLength > 0) {
    // 递归构建左子树
    root->left = rebuildTree(preorderNums, inorderNums, startPreorder + 1,
                             leftTreerEnd, startInorder, inorder_index - 1);
  }
  if (leftTreeLength < endPreorder - startInorder) {
    // 递归构建右子树
    root->right = rebuildTree(preorderNums, inorderNums, leftTreerEnd + 1,
                              endPreorder, inorder_index + 1, endInorder);
  }
  return root;
}
